package com.ycy.leetcode.tree;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.*;


/**
 * 层序遍历  广度优先搜索
 * 层序遍历  深度优先搜索 前序遍历
 *
 * 前序遍历  迭代法
 * 最大树深度
 * 合并二叉树
 */
public class TreeBianLi {

  TreeNode root = null;

  @Before
  public void before() {

    /*
           5
          /\
      200     1000
      /\       /\
    100 300 700 1500
     */
    TreeNode root = new TreeNode(5);
    root.l = new TreeNode(200);
    root.l.l = new TreeNode(100);
    root.l.r = new TreeNode(300);

    root.r = new TreeNode(1000);
    root.r.l = new TreeNode(700);
    root.r.r = new TreeNode(1500);
    this.root = root;
  }

  TreeNode root2 = null;

  @Before
  public void before2() {

    /*
         1000
          /\
      400     2000
      /\       /\
    200 300
     */
    TreeNode root = new TreeNode(1000);

    root.l = new TreeNode(400);
    root.l.l = new TreeNode(200);
    root.l.r = new TreeNode(300);

    root.r = new TreeNode(2000);
//    root.r.l = new TreeNode(700);
//    root.r.r = new TreeNode(1500);
    this.root2 = root;
  }

  @Test
  public void test() {
    List<List<Integer>> lists = levelOrder(root);
    System.out.println(lists);
  }

  /**
   * 层序遍历 BFS(广度优先搜索)
   * offer 插入
   * peek 查头部
   * poll 弹出
   */
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
      int size = q.size();
      List<Integer> level = new LinkedList<>();
      for (int i = 0; i < size; ++i) {
        TreeNode cur = q.peek();
        q.poll();
        if (cur == null) {
          continue;
        }
        level.add(cur.val);
        q.offer(cur.l);
        q.offer(cur.r);
      }
      if (!level.isEmpty()) {
        res.add(level);
      }
    }
    return res;
  }



  List<List<Integer>> levelOrder = Lists.newArrayList();

  /**
   * 层序遍历
   */
  public void levelOrderdfs(TreeNode root, int dep) {
    if (root == null) return;
    if (levelOrder.size() < dep) levelOrder.add(new ArrayList<>());
    levelOrder.get(dep - 1).add(root.val);
    levelOrderdfs(root.l, dep + 1);
    levelOrderdfs(root.r, dep + 1);
  }

  @Test
  public void test1() {
    levelOrderdfs(root, 1);
    System.out.println(levelOrder);
  }

  /**
   * 前序遍历 迭代法
   */
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<Integer> output = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      output.add(node.val);
      if (node.r != null) {
        stack.add(node.r);
      }
      if (node.l != null) {
        stack.add(node.l);
      }
    }

    return output;
  }

  @Test
  public void test2() {
    List<Integer> integers = preorderTraversal(root);
    System.out.println(integers);
  }

  /**
   * dfs 求最大数深度
   */
  public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int r = maxDepth(root.r);
    int l = maxDepth(root.l);
    return Math.max(r, l) + 1;
  }

  /**
   * 合并二叉树
   */
  public TreeNode merge(TreeNode root1, TreeNode root2) {

    if (root1 == null) {
      return root2;
    }

    if (root2 == null) {
      return root1;
    }

    root1.val = root1.val + root2.val;

    root1.l = merge(root1.l, root2.l);
    root1.r = merge(root1.r, root2.r);

    return root1;
  }

  //合并二叉树
  @Test
  public void test3() {
    System.out.println(levelOrder(root));
    System.out.println(levelOrder(root2));
    merge(root, root2);
    levelOrderdfs(root, 1);
    System.out.println(levelOrder);
  }


  public static class TreeNode {
    int val;
    TreeNode l;
    TreeNode r;

    TreeNode(int x) {
      val = x;
    }

  }

}
